{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Validate Stack Sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validateStackSequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证栈序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定&nbsp;<code>pushed</code>&nbsp;和&nbsp;<code>popped</code>&nbsp;两个序列，每个序列中的 <strong>值都不重复</strong>，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 <code>true</code>；否则，返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>pushed = [1,2,3,4,5], popped = [4,5,3,2,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>我们可以按以下顺序执行：\n",
    "push(1), push(2), push(3), push(4), pop() -&gt; 4,\n",
    "push(5), pop() -&gt; 5, pop() -&gt; 3, pop() -&gt; 2, pop() -&gt; 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>pushed = [1,2,3,4,5], popped = [4,3,5,1,2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>1 不能在 2 之前弹出。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pushed.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= pushed[i] &lt;= 1000</code></li>\n",
    "\t<li><code>pushed</code> 的所有元素 <strong>互不相同</strong></li>\n",
    "\t<li><code>popped.length == pushed.length</code></li>\n",
    "\t<li><code>popped</code> 是 <code>pushed</code> 的一个排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [validate-stack-sequences](https://leetcode.cn/problems/validate-stack-sequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [validate-stack-sequences](https://leetcode.cn/problems/validate-stack-sequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n[4,5,3,2,1]', '[1,2,3,4,5]\\n[4,3,5,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        numset = set()\n",
    "        stack = []\n",
    "        pushed_idx, length = 0, len(pushed)\n",
    "        for num in popped:\n",
    "            if not stack:\n",
    "                stack.append(pushed[pushed_idx])\n",
    "                numset.add(pushed[pushed_idx])\n",
    "                pushed_idx += 1\n",
    "            while num != stack[-1]:               \n",
    "                if num not in numset and pushed_idx < length:\n",
    "                    stack.append(pushed[pushed_idx])                    \n",
    "                    numset.add(pushed[pushed_idx])\n",
    "                    pushed_idx += 1\n",
    "                else:\n",
    "                    return False\n",
    "            stack.pop()\n",
    "        return True\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        flag = 0\n",
    "        equal = False\n",
    "        for i in range(len(pushed)):\n",
    "            if pushed[i] == popped[flag]:\n",
    "                flag += 1\n",
    "                equal = True\n",
    "                while equal:\n",
    "                    if stack:\n",
    "                        if stack[-1] == popped[flag]:\n",
    "                            stack.pop()\n",
    "                            flag += 1\n",
    "                        else:\n",
    "                            equal = False\n",
    "                    else:\n",
    "                        equal = False\n",
    "            else:\n",
    "                stack.append(pushed[i])\n",
    "        print(stack)\n",
    "        if stack:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        pop = 0\n",
    "        for push in pushed:\n",
    "            stack.append(push)\n",
    "            while stack and stack[-1] == popped[pop]:\n",
    "                stack.pop()\n",
    "                pop += 1\n",
    "            \n",
    "        if stack:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(pushed)!=len(popped):\n",
    "            return False\n",
    "        \n",
    "        stack,i=[],0\n",
    "        \n",
    "        for n in pushed:\n",
    "            stack.append(n)\n",
    "            print(i,'append:\\t',n)\n",
    "            while stack and stack[-1]==popped[i]:\n",
    "                v=stack.pop()\n",
    "                print(i,'pop:\\t',v)\n",
    "                i+=1\n",
    "        print('final: %s\\t%s' %(stack,i))\n",
    "        \n",
    "        if stack:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        temp_stack = []\n",
    "        for s in pushed:\n",
    "            temp_stack.append(s)\n",
    "            try:\n",
    "                while temp_stack[-1] == popped[0]:\n",
    "                    temp_stack.pop()\n",
    "                    popped = popped[1:]\n",
    "            except Exception as e:\n",
    "                print('error')\n",
    "\n",
    "        if temp_stack == []:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        cnt = len(pushed)\n",
    "        if cnt == 0 or cnt == 1:\n",
    "            return True\n",
    "        \n",
    "        stack = []\n",
    "\n",
    "        while len(pushed) != 0:\n",
    "            stack.append(pushed.pop(0))\n",
    "            \n",
    "            while len(stack) != 0 and stack[len(stack) - 1] == popped[0]:\n",
    "                stack.pop(len(stack) - 1)\n",
    "                popped.pop(0)\n",
    "            \n",
    "        if len(stack) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        pushi, popi = 0, 0\n",
    "        pushlen, poplen = len(pushed), len(popped)\n",
    "        while popi < poplen:\n",
    "            if pushi < pushlen and pushed[pushi] == popped[popi]:\n",
    "                popi += 1\n",
    "                pushi += 1\n",
    "            elif stack and pushed[stack[-1]] == popped[popi] :\n",
    "                stack.pop()\n",
    "                popi += 1\n",
    "            elif pushi < pushlen:\n",
    "                stack.append(pushi)\n",
    "                pushi += 1\n",
    "            else:\n",
    "                break\n",
    "        return not stack\n",
    "                \n",
    "            \n",
    "                \n",
    "               \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        \"\"\"\n",
    "        :type pushed: List[int]\n",
    "        :type popped: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack=[]\n",
    "        #j是下一个，所以最后一个等于len的时候就结束了\n",
    "        j=0\n",
    "        for x in pushed:\n",
    "            stack.append(x)\n",
    "            while stack and popped[j]==stack[-1]:\n",
    "                j+=1\n",
    "                print(j,stack[-1])\n",
    "                stack.pop()\n",
    "\n",
    "        return j==len(popped)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: 'List[int]', popped: 'List[int]') -> 'bool':\n",
    "        j = 0\n",
    "        s = []\n",
    "        for x in pushed:\n",
    "            s.append(x)\n",
    "            while s and j < len(popped) and s[-1] == popped[j]:\n",
    "                s.pop()\n",
    "                j += 1\n",
    "        return j == len(popped)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def validateStackSequences(self, pushed, popped):\n",
    "        j = 0\n",
    "        stack = []\n",
    "        for x in pushed:\n",
    "            stack.append(x)\n",
    "            while stack and j < len(popped) and stack[-1] == popped[j]:\n",
    "                stack.pop()\n",
    "                j += 1\n",
    "\n",
    "        return j == len(popped)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        pionter = 0\n",
    "        stack = []\n",
    "\n",
    "        for i in pushed:\n",
    "            stack.append(i)\n",
    "            while (stack !=[] and stack[-1] == popped[pionter]):\n",
    "                stack.pop()\n",
    "                pionter += 1\n",
    "        \n",
    "        while(stack !=[] and stack[-1] == popped[pionter]):\n",
    "            stack.pop()\n",
    "            pionter += 1\n",
    "        \n",
    "        if stack == []:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        self.stack = []\n",
    "        for item in pushed:\n",
    "            self.stack.append(item)\n",
    "            while self.stack and popped and self.stack[-1] == popped[0]:\n",
    "                del self.stack[-1], popped[0]\n",
    "        if self.stack:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        if len(pushed) in [0,1]:\n",
    "            return True\n",
    "        stack = []\n",
    "        while pushed or popped:\n",
    "            wait_to_popped = popped[0]\n",
    "            while not stack or stack[-1]!=wait_to_popped:\n",
    "                if not pushed:\n",
    "                    return False\n",
    "                else:\n",
    "                    stack.append(pushed.pop(0))\n",
    "            stack.pop()\n",
    "            popped.pop(0)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack = []\n",
    "        cur1, cur2 = 0, 0\n",
    "        while(cur1<len(pushed) and cur2<len(popped)):\n",
    "            stack.append(pushed[cur1])\n",
    "            cur1 += 1\n",
    "            while(stack and cur2<len(popped) and stack[-1] == popped[cur2]):\n",
    "                stack.pop()\n",
    "                cur2 += 1\n",
    "        return not (stack or cur1 < len(pushed) or cur2 < len(popped))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        self.help_queue = []\n",
    "        while pushed:\n",
    "            self.help_queue.append(pushed[0])\n",
    "            pushed.pop(0)\n",
    "            while self.help_queue:\n",
    "                if popped[0] == self.help_queue[-1]:\n",
    "                    popped.pop(0)\n",
    "                    self.help_queue.pop()\n",
    "                else:\n",
    "                    break\n",
    "        if popped:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack = []\n",
    "        for num in pushed:\n",
    "            stack.append(num)\n",
    "            while stack and  stack[-1] == popped[0]:\n",
    "                stack.pop()\n",
    "                popped.pop(0)\n",
    "        return False if stack else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack = []\n",
    "        length = len(pushed)\n",
    "        i, j = 0, 0\n",
    "        instack = set()\n",
    "        while j < length:\n",
    "            if stack and stack[-1] == popped[j]:\n",
    "                stack.pop()\n",
    "                j += 1\n",
    "                continue\n",
    "            if i >= length or popped[j] in instack:\n",
    "                return False\n",
    "            if pushed[i] == popped[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                stack.append(pushed[i])\n",
    "                instack.add(pushed[i])\n",
    "                i += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        self.help_queue = []\n",
    "        while pushed:\n",
    "            self.help_queue.append(pushed[0])\n",
    "            pushed.pop(0)\n",
    "            while self.help_queue:\n",
    "                if popped[0] == self.help_queue[-1]:\n",
    "                    popped.pop(0)\n",
    "                    self.help_queue.pop()\n",
    "                else:\n",
    "                    break\n",
    "            print(self.help_queue)\n",
    "        print(popped)\n",
    "        if popped:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        def F(l1, r1, l2, r2):\n",
    "            # print((l1, r1), (l2, r2))\n",
    "            if l1 > r1:\n",
    "                return True\n",
    "            elif l1 == r1:\n",
    "                return pushed[l1] == popped[l2]\n",
    "            elif l1 == r1 - 1:\n",
    "                return len(set(pushed[l1:r1+1]).union(set(popped[l2:r2+1]))) == 2\n",
    "            else:\n",
    "                x = pushed[l1]\n",
    "                for i in range(l2, r2+1):\n",
    "                    if x == popped[i]:\n",
    "                        L = i - l2 + 1\n",
    "                        return F(l1+1, l1+L-1, l2, i-1) and F(l1+L, r1, i+1, r2)\n",
    "                return False\n",
    "        \n",
    "        N = len(pushed)\n",
    "        return F(0, N-1, 0, N-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#栈的出场顺序是不是合法\n",
    "#创建一个栈\n",
    "import pdb\n",
    "class Stack():\n",
    "    def __init__(self):\n",
    "        self.values=[]\n",
    "    \n",
    "    def push(self,num):\n",
    "        self.values.append(num)\n",
    "    \n",
    "    def pop(self):\n",
    "        self.values.remove(self.values[-1])\n",
    "    \n",
    "    def top(self):\n",
    "        if len(self.values)==0:\n",
    "            return None\n",
    "        else:\n",
    "            return self.values[-1]\n",
    "    \n",
    "    def empty(self):\n",
    "        if len(self.values)==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack=Stack()\n",
    "        for i in pushed:\n",
    "            stack.push(i)\n",
    "            while (stack.empty()==False) & (stack.top()==popped[0]):\n",
    "                stack.pop()\n",
    "                popped.remove(popped[0])\n",
    "                print(len(popped))\n",
    "                if len(popped)==0:\n",
    "                    return True\n",
    "  \n",
    "        if len(popped)==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        pushed = collections.deque(pushed)\n",
    "        popped = collections.deque(popped)\n",
    "        stack = []\n",
    "        while pushed:\n",
    "            a = pushed.popleft()\n",
    "            if a != popped[0]:\n",
    "                while stack and stack[-1]==popped[0]:\n",
    "                    stack.pop()\n",
    "                    popped.popleft()\n",
    "                stack.append(a)\n",
    "            else:\n",
    "                popped.popleft()\n",
    "        return stack[::-1] == list(popped)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        st, j = [], 0\n",
    "        for x in pushed:\n",
    "            st.append(x)\n",
    "            while st and st[-1] == popped[j]:\n",
    "                st.pop()\n",
    "                j += 1\n",
    "        return len(st) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        dic=set()\n",
    "        while popped!=[]:\n",
    "            if len(stack)>0 and popped[0] in dic:\n",
    "                if stack[-1]!=popped[0]:\n",
    "                    return False\n",
    "                else:\n",
    "                    val=stack.pop()\n",
    "                    dic.remove(val)\n",
    "                    popped.pop(0)\n",
    "                    continue\n",
    "            \n",
    "            else:\n",
    "                val=pushed.pop(0)\n",
    "                stack.append(val)\n",
    "                dic.add(val)\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        while popped!=[]:\n",
    "            if len(stack)>0 and popped[0] in stack:\n",
    "                if stack[-1]!=popped[0]:\n",
    "                    return False\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    popped.pop(0)\n",
    "                    continue\n",
    "            \n",
    "            else:\n",
    "                stack.append(pushed.pop(0))\n",
    "                \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack = []\n",
    "        try_pop = []\n",
    "        push_start = 0\n",
    "        pop_index = 0\n",
    "        while len(try_pop) <= len(pushed):\n",
    "            # print(\"push start:\", push_start)\n",
    "            if pop_index >= len(popped):\n",
    "                break\n",
    "\n",
    "            if popped[pop_index] not in stack and push_start <= len(pushed) - 1:\n",
    "                push_end = pushed.index(popped[pop_index])\n",
    "                # print(\"push end:\",push_end)\n",
    "                for j in range(push_start, push_end + 1):\n",
    "                    stack.append(pushed[j])\n",
    "                    if j == push_end:\n",
    "                        try_pop.append(stack.pop())\n",
    "                        pop_index += 1\n",
    "                push_start = push_end + 1\n",
    "                        \n",
    "            else:\n",
    "                # popped[i] in stack:\n",
    "                if stack and popped[pop_index] == stack[-1]:\n",
    "                    try_pop.append(stack.pop())\n",
    "                    pop_index += 1\n",
    "                elif popped[pop_index] != stack[-1]:\n",
    "                    print(popped[pop_index],stack)\n",
    "                    return False\n",
    "        \n",
    "            print(stack, try_pop)\n",
    "\n",
    "        return try_pop == popped\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        st = []\n",
    "        j = 0\n",
    "        for i in pushed:\n",
    "            st.append(i)\n",
    "            print(st)\n",
    "            while st and st[-1] == popped[j]:\n",
    "                st.pop()\n",
    "                j += 1\n",
    "            \n",
    "        return len(st)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        stack,i = [] , 0\n",
    "        for num in pushed:\n",
    "            stack.append(num)\n",
    "            while stack and popped[i]==stack[-1]:\n",
    "                stack.pop()\n",
    "                i+=1\n",
    "        return i == len(popped)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        while i<len(pushed) or  stack:\n",
    "            if i<len(pushed)  and pushed[i] == popped[j]:\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif stack and stack[-1] == popped[j]:\n",
    "                stack.pop()\n",
    "                j+=1\n",
    "            else:\n",
    "                if not i <len(pushed):\n",
    "                    if len(stack) == 0:\n",
    "                        return True\n",
    "                    return False\n",
    "                stack.append(pushed[i])\n",
    "                i+=1\n",
    "        return True if not stack else False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:\n",
    "        st = []\n",
    "        n = len(pushed)\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            st.append(i)\n",
    "            while st and pushed[st[-1]] == popped[j]:\n",
    "                st.pop()\n",
    "                j += 1\n",
    "        \n",
    "        return not st"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
